package com.breeze.leetcode.middle;

import java.awt.geom.Area;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @url <a href="https://leetcode.cn/problems/pacific-atlantic-water-flow">417. 太平洋大西洋水流问题</a>
 * @author yangzh
 * @date 2025/2/24
 */
public class T417 {
    private Memo[][] memos;

    public static void main(String[] args) {
        T417 solution = new T417();
        int[][] heights = {{1,2,2,3,5},{3,2,3,4,4},{2,4,5,3,1},{6,7,1,4,5},{5,1,1,2,4}};
        List<List<Integer>> result = solution.pacificAtlantic(heights);
        result.forEach(System.out::println);
    }


    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> res = new ArrayList<>();
        this.memos = new Memo[heights.length][heights[0].length];
        for (int i = 0; i < heights.length; i++) {
            for (int j = 0; j < heights[i].length; j++) {
                memos[i][j] = dfs(i, j, 0, heights);
                if (memos[i][j].fd == 0) res.add(Arrays.asList(i, j));
            }
        }

        return res;
    }

    /**
     * 计算当前位置的流动方向
     * @param inflow 流入方向；0初始位置，1向上，禁止向下;2向右，禁止向左;3向下，禁止向上;4向左，禁止向右
     */
    private Memo dfs(int i, int j, int inflow, int[][] heights) {
        Memo memo = new Memo();
        // 如果靠左或靠上，则是靠近太平洋
        if (i == 0 || j == 0) {
            memo.setFd(1);
        }

        // 如果靠右或靠下，则是靠近大西洋
        if (i == heights.length - 1 || j == heights[i].length - 1) {
            memo.setFd(-1);
        }

        // 向下
        if (inflow != 1 && i < heights.length - 2 && heights[i][j] >= heights[i + 1][j]) {
            memo.setFd(dfs(i + 1, j, 3, heights));
        }

        // 向左
        if (inflow != 2 && j > 0 && heights[i][j] >= heights[i][j - 1]) {
            memo.setFd(dfs(i, j - 1, 4, heights));
        }

        // 向上
        if (inflow != 3 && i > 0 && heights[i][j] >= heights[i - 1][j]) {
            memo.setFd(dfs(i - 1, j, 1, heights));
        }

        // 向右
        if (inflow != 4 && j < heights[i].length - 2 && heights[i][j] >= heights[i][j + 1]) {
            memo.setFd(dfs(i, j + 1, 2, heights));
        }
        memos[i][j] = memo;
        return memo;
    }

    static class Memo {
        Integer fd;
        public Memo() {
            fd = null;
        }

        public void setFd(Memo fd) {
            if (fd != null && fd.fd != null) {
                this.setFd(fd.fd);
            }
        }

        public void setFd(Integer fd) {
            if (this.fd == null) {
                this.fd = fd;
            }else if (this.fd == 0 || fd == 0) {
                this.fd = 0;
            }else if (!this.fd.equals(fd)) {
                this.fd = 0;
            }
        }
    }
}
